package main

// 枚举高， 求出该高度对应的宽度， 也就是求左边第一个比我小的位置，右边第一个比我小的位置，才能保证高
func largestRectangleArea(heights []int) int {
	n := len(heights)
	left, right := make([]int, n), make([]int, n)
	stack := make([]int, 0)
	// 求左边最后一个（最接近我）比我小的: 递增栈
	for i, num := range heights {
		// 必须先删除栈中大于（等于！）的元素，再在栈中进行比较
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= num {
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 && heights[stack[len(stack)-1]] < num {
			left[i] = stack[len(stack)-1]
		} else {
			left[i] = -1
		}
		stack = append(stack, i)
	}
	stack = make([]int, 0)
	// 求右边第一个比我小的
	for i := range right {
		right[i] = n
	}
	for i, num := range heights {
		for len(stack) > 0 && heights[stack[len(stack)-1]] > num {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			right[idx] = i
		}
		stack = append(stack, i)
	}
	// 计算最大值
	maxArea := 0
	for i := range heights {
		width := right[i] - left[i] - 1
		area := width * heights[i]
		if area > maxArea {
			maxArea = area
		}
	}
	return maxArea
}
